package leetcode.editor.cn;

//给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab",
//"cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
//
// 注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
//
// 返回一个表示每个字符串片段的长度的列表。
//
//
//示例 1：
//
//
//输入：s = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
//
// 示例 2：
//
//
//输入：s = "eccbbbbdec"
//输出：[10]
//
//
//
//
// 提示：
//
//
// 1 <= s.length <= 500
// s 仅由小写英文字母组成
//
//
// Related Topics 贪心 哈希表 双指针 字符串 👍 1250 👎 0

import java.util.ArrayList;
import java.util.List;

//Java：划分字母区间
public class PartitionLabels{
    public static void main(String[] args) {
        Solution solution = new PartitionLabels().new Solution();
        solution.partitionLabels("ababcbacadefegdehijhklij");
        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public List<Integer> partitionLabels(String s) {
            int[] last = new int[26];
            int length = s.length();
            for (int i = 0; i < length; i++) {//使用数组记录字符串中每个字母出现的最后位置
                last[s.charAt(i) - 'a'] = i;
            }
            List<Integer> partition = new ArrayList<Integer>();
            int start = 0, end = 0;
            for (int i = 0; i < length; i++) {
                end = Math.max(end, last[s.charAt(i) - 'a']);//维护当前片段能提供的最远距离
                if (i == end) {//如果遍历到当前位置，则说明当前片段已经结束，可以添加到结果中，并更新起始位置
                    partition.add(end - start + 1);
                    start = end + 1;
                }
            }
            return partition;
        }


}
//leetcode submit region end(Prohibit modification and deletion)

}
